'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-06 15:24:05
'''
#
# @lc app=leetcode.cn id=3 lang=python3
#
# [3] 无重复字符的最长子串
#

# @lc code=start
# hash外加dp嘛
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        import collections
        store = collections.defaultdict(lambda:-1)
        # print(store)
        ans = 0
        dp=1
        for i, v in enumerate(s):
            dp = dp+1 if i-store[v]>dp else i-store[v]
            ans = max(ans, dp)
            store[v]=i
        return ans
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    s = "abcabcbb"
    print(solution.lengthOfLongestSubstring(s))